import java.util.Stack;

class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;

    //TreeNode的构造方法
    public TreeNode(char val) {
        this.val = val;
    }
}

class MyBinaryTree {
    //人为拼接构造一颗二叉树的方法
    public TreeNode creatTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        TreeNode I = new TreeNode('I');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        F.left = I;
        return A;//返回根节点A
    }

    //查找二叉树中是否包含值为key的节点的方法
    public TreeNode find(TreeNode root, char key) {
        //空节点返回空
        if (root == null) {
            return null;
        }
        //找到key值节点则返回
        if (root.val == key) {
            return root;
        }
        //递归左子树
        TreeNode leftVal = find(root.left, key);
        if (leftVal != null) {
            return leftVal;
        }
        //递归右子树
        TreeNode rightVal = find(root.right, key);
        if (rightVal != null) {
            return rightVal;
        }
        //程序全部运行结束说明没有招到值为key的节点
        return null;
    }

    //前序遍历方法
    public void preOrder(TreeNode root) {
        //空节点返回
        if (root == null) {
            return;
        }
        //打印根节点
        System.out.print(root.val + " ");
        //递归左子树
        preOrder(root.left);
        //递归右子树
        preOrder(root.right);

    }

    //中序遍历方法
    public void inOrder(TreeNode root) {
        //空节点返回
        if (root == null) {
            return;
        }
        //递归左子树
        inOrder(root.left);
        //打印根节点
        System.out.print(root.val + " ");
        //递归右子树
        inOrder(root.right);

    }

    //后序遍历方法
    public void postOrder(TreeNode root) {
        //空节点返回
        if (root == null) {
            return;
        }
        //递归左子树
        postOrder(root.left);
        //递归右子树
        postOrder(root.right);
        //打印根节点
        System.out.print(root.val + " ");

    }

    //获取树中的节点个数的方法
    public int getSize(TreeNode root) {
        //空节点返回0
        if (root == null) {
            return 0;
        }
        //递归左子树和右子树（+1为根节点个数）
        int size = 1 + getSize(root.left) + getSize(root.right);
        return size;
    }

    //获取二叉树中叶子节点个数的方法
    public int getLeafNodeCount(TreeNode root) {
        //空节点返回0
        if (root == null) {
            return 0;
        }
        //叶子节点返回1
        if (root.left == null && root.right == null) {
            return 1;
        }
        //递归左子树和右子树
        int count = getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
        return count;
    }

    //获取第k层(根节点层数为0)的节点个数的方法
    public int getKthLevelNodeCount(TreeNode root, int k) {
        //空节点返回0
        if (root == null) {
            return 0;
        } else if (k == 0) {
            //本层节点返回1
            return 1;
        }
        //递归左子树和右子树
        return getKthLevelNodeCount(root.left, k - 1) + getKthLevelNodeCount(root.right, k);

    }

    //获取二叉树的深度的方法
    public int getHight(TreeNode root) {
        //空节点返回-1
        if (root == null) {
            return -1;
        }
        //递归左子树
        int leftHeight = getHight(root.left);
        //递归右子树
        int rightHeight = getHight(root.right);
        //返回其中最大值
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
}
public class InOrderNot {
    public void inOrderNot(TreeNode root){
        //创建一个新的栈
        Stack<TreeNode>stack=new Stack<>();
        //用cur记录当前遍历节点
        TreeNode cur=root;
        //根据先序遍历从下到上的顺序可知，若cur不为空或者栈不为空循环继续，使得cur从下至上遍历
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                //向左子树遍历为最高优先级
                cur=cur.left;
            }
            //弹出此节点,用top记录，以便向打印此节点和右子树遍历
            TreeNode top=stack.pop();
            //输出根节点值为次高优先级
            System.out.print(top.val+" ");
            //向右子树遍历为最低优先级
            cur=top.right;
        }

    }
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree=new MyBinaryTree();
        InOrderNot inOrderNot=new InOrderNot();
        TreeNode root=myBinaryTree.creatTree();

        //递归方法实现中序遍历演示
        System.out.print("递归实现:  ");
        myBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("*****************************");
        System.out.print("非递归实现:");
        inOrderNot.inOrderNot(root);
    }
}